package datastructure.link;

import java.util.ArrayList;
import java.util.List;

public class LC142 {
    //最垃圾的算法，利用额外空间存储已经遍历过的节点，如果发现有重复了，说明有环形节点， 返回该重复节点既可
    public ListNode detectCycle1(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            if (list.contains(current)) {
                return current;
            }
            list.add(current);
            current = current.next;
        }
        return null;
    }

    //利用快慢指针，快慢指针相遇的地方一定在环内，因为在环外快指针一定比满指针快，如果不是环状链表，快指针会先指向null
    //如果出现slow == fast的情况，说明已经相遇了，即说明链表有环
    //判断有环之后，需要找到环的入口，通过数据计算得出，一个节点从head开始遍历，一个节点从相遇节点开始遍历，并且一次遍历一个节点，当他们再次相遇的时候就是环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        //这里只判断fast不为null
        while (fast!= null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            //如果有环
            if (slow == fast) {
                ListNode index1= fast;
                ListNode index2 = head;
                //寻找环的入口
                while (index2!=index1) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                if (index1 != null) {
                    return index1;
                }
            }
        }
        return null;
    }
}
